package com.zjsru.oneDay202205;

/**
 * @Author: likew
 * @Date: 2022/5/4
 * 找出游戏的获胜者
 * 输入：n = 5, k = 2
 * 输出：3
 * 解释：游戏运行步骤如下：
 * 1) 从小伙伴 1 开始。
 * 2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。
 * 3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
 * 4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。
 * 5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
 * 6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。
 * 7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
 * 8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。
 * 9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
 *
 */
public class findTheWinner {
    public int findTheWinner(int n, int k) {
        boolean[] vis = new boolean[n +10];
        int cnt = 0, cur = 0;
        while(cnt != n - 1){
            for (int i = 0; i < k - 1; i++) {
                cur++;
                while(vis[cur % n]) cur++;
            }
            vis[cur % n] = true;
            cnt++; cur++;
            while(vis[cur % n]) cur++;
        }
        return (cur % n)+1;
    }
    
    public static void main(String[] args) {
        findTheWinner findTheWinner = new findTheWinner();
        int n = 5, k = 2;
        System.out.println(findTheWinner.findTheWinner(n, k));
    }
}
